﻿/*------------------------------------------------------------------------

CXXLLIST.HPP v3,0,2

Copyright 楊志賢 CxxlMan, 2008 - 2011
All Rights Reserved

------------------------------------------------------------------------*/

#if !defined(__CXXLLIST_HPP_CxxlMan)
#define __CXXLLIST_HPP_CxxlMan

#include "SMART_PTR.HPP"

namespace CxxlMan
{

enum PT_PS_TYPE
{
  toHead,
  toTail
};


template <class T>
class cxxlList:virtual public cxxlObject
{
  struct Node
  {
    Smart_Ptr<T> Obj_Ptr;
    Node *prev,*next;

    // Constructor
    Node(T *S,cxxlList<T> *Host)
      :Obj_Ptr(S,Host)
    {
    }
  };

  ISpirit *m_spirit; // 記住以拱 CreateSelf() 用

  unsigned long count;
  Node *head,*tail,*PT;
  CriticalSec csObject;

  // 使用特殊的快速排序法，可遞迴的排序 P 至 N 的節點
  void cxxlFASTCALL doSort(Node *P,Node *N);

  // 排序檢測，延伸類別須改寫此函數
  // 要讓 P 排在 前(Head) 回答 true，否則 false
  virtual bool cxxlFASTCALL Diagnosis(const T *P, const T *N) const
  {
    return true;
  }

  void cxxlFASTCALL Swap(Node *L,Node *R)
  {
    Smart_Ptr<T> temp(L->Obj_Ptr);
    L->Obj_Ptr = R->Obj_Ptr;
    R->Obj_Ptr = temp;
  }

  // Clone() 時用來產生延伸類別的物件
  // 所以延伸別必須覆載
  virtual cxxlList<T> * cxxlFASTCALL CreateSelf(ISpirit *spirit) const
  {
    return new cxxlList<T>(spirit);
  }

public:
  // Constructor
  cxxlList(ISpirit *spirit = Spirit_Easy)
    :cxxlObject(spirit)
  {
    head = new Node(NULL,this);
    tail = new Node(NULL,this);

    head->next = tail;
    tail->prev = head;
    PT = head;
    count = 0;
  }

  // Destructor
  virtual ~cxxlList()
  {
    ClearAll();
    delete head;
    delete tail;
  }

  // 刪除(放棄持有)所有物件
  void cxxlFASTCALL ClearAll();

  // 將物件放入最前位置
  void cxxlFASTCALL Push_Front(const Smart_Ptr<T> &S);

  // 將物件放入最後位置
  void cxxlFASTCALL Push_Back(const Smart_Ptr<T> &S);

  // 刪除(放棄持有)最前面一個物件
  void cxxlFASTCALL Delete_Front();

  // 刪除(放棄持有)最後一個物件
  void cxxlFASTCALL Delete_Back();

  // 取得物件存放的個數
  unsigned long cxxlFASTCALL GetCount() const
  {
    return count;
  }

  // 取得最前一個物件
  Smart_Ptr<T> cxxlFASTCALL GetObj_Front() const
  {
    CriticalSecHandle AutoCSH(csObject);
    if(head->next != tail)
      return head->next->Obj_Ptr;
    else
      return Smart_Ptr<T>(NULL);
  }

  // 取得最後一個物件
  Smart_Ptr<T> cxxlFASTCALL GetObj_Back() const
  {
    CriticalSecHandle AutoCSH(csObject);
    if(tail->prev != head)
      return tail->prev->Obj_Ptr;
    else
      return Smart_Ptr<T>(NULL);
  }

  // 取出最前一個物件並刪除(放棄持有)
  Smart_Ptr<T> cxxlFASTCALL Pop_Front()
  {
    CriticalSecHandle AutoCSH(csObject);
    if(head->next != tail)
    {
      Smart_Ptr<T> temp = head->next->Obj_Ptr;
      Delete_Front();
      return temp;
    }
    else
      return Smart_Ptr<T>(NULL);
  }

  // 取出最後一個物件並刪除(放棄持有)
  Smart_Ptr<T> cxxlFASTCALL Pop_Back()
  {
    CriticalSecHandle AutoCSH(csObject);
    if(tail->prev != head)
    {
      Smart_Ptr<T> temp = tail->prev->Obj_Ptr;
      Delete_Back();
      return temp;
    }
    else
      return Smart_Ptr<T>(NULL);
  }

  // 設定指位器至 最前(toHead)或最後(toTail) 的物件位置
  // 非空容器會移到 第一個 或 最後一個 有物件的位置
  // 若是空容器會移到 最後 或 最前 NULL 節點
  void cxxlFASTCALL ResetPT(PT_PS_TYPE P)
  {
    csObject.Enter();
    if(P == toHead)
      PT = head->next;
    else
      PT = tail->prev;
    csObject.Leave();
  }

  // 取得指位器目前所指的物件
  Smart_Ptr<T> cxxlFASTCALL GetObj() const
  {
    CriticalSecHandle AutoCSH(csObject);
    return PT->Obj_Ptr;
  }

  // 指位器往後(++)或前(--)的位置移動，並回傳移動前所指的物件
  Smart_Ptr<T> cxxlFASTCALL operator ++ (int)  // c++
  {
    CriticalSecHandle AutoCSH(csObject);
    T *obj_ptr = PT->Obj_Ptr;
    if(PT != tail)
      PT = PT->next;
    return Smart_Ptr<T>(obj_ptr);
  }
  Smart_Ptr<T> cxxlFASTCALL operator -- (int)  // c--
  {
    CriticalSecHandle AutoCSH(csObject);
    T *obj_ptr = PT->Obj_Ptr;
    if(PT != head)
      PT = PT->prev;
    return Smart_Ptr<T>(obj_ptr);
  }

  // 啟動排序
  void cxxlFASTCALL Sort()
  {
    csObject.Enter();

    if(head->next != tail)
      if(head->next->next != tail)
        doSort(head->next,tail->prev);

    PT = head;

    csObject.Leave();
  }

  // 自我複製
  // 傳回相同內容的同類形容器物件
  Smart_Ptr<cxxlList<T> > cxxlFASTCALL Clone() const;
};

// 自我複製
// 傳回相同內容的同類形容器物件
template <class T>
Smart_Ptr<cxxlList<T> > cxxlFASTCALL cxxlList<T>::Clone() const
{
  CriticalSecHandle AutoCSH(csObject);

  cxxlList<T> *R = CreateSelf(m_spirit);

  Node *temp = head->next;
  while(temp != tail)
  {
    R->Push_Back(temp->Obj_Ptr);
    temp = temp->next;
  }

  return Smart_Ptr<cxxlList<T> >(R);
}


// 刪除(放棄持有)最後一個物件
template <class T>
void cxxlFASTCALL cxxlList<T>::Delete_Back()
{
  csObject.Enter();
  Node *temp = tail->prev;
  if(temp != head)
  {
    tail->prev = temp->prev;
    temp->prev->next = tail;
    if(PT == temp) PT = tail;
    delete temp;
    count--;
  }
  csObject.Leave();
}

// 刪除(放棄持有)最前面一個物件
template <class T>
void cxxlFASTCALL cxxlList<T>::Delete_Front()
{
  csObject.Enter();
  Node *temp = head->next;
  if(temp != tail)
  {
    head->next = temp->next;
    temp->next->prev = head;
    if(PT == temp) PT = head;
    delete temp;
    count--;
  }
  csObject.Leave();
}


// 將物件放入最後位置
template <class T>
void cxxlFASTCALL cxxlList<T>::Push_Back(const Smart_Ptr<T> &S)
{
  csObject.Enter();
  Node *temp = new Node(S,this);
  temp->prev = tail->prev;
  temp->next = tail;
  tail->prev->next = temp;
  tail->prev = temp;
  count++;
  csObject.Leave();
}

// 將物件放入最前位置
template <class T>
void cxxlFASTCALL cxxlList<T>::Push_Front(const Smart_Ptr<T> &S)
{
  csObject.Enter();
  Node *temp = new Node(S,this);
  temp->next = head->next;
  temp->prev = head;
  head->next->prev = temp;
  head->next = temp;
  count++;
  csObject.Leave();
}

// 刪除(放棄持有)所有物件
template <class T>
void cxxlFASTCALL cxxlList<T>::ClearAll()
{
  csObject.Enter();
  Node *temp;
  while((temp = head->next) != tail)
  {
    head->next = temp->next;
    delete temp;
  }
  tail->prev = head;
  PT = head;
  count = 0;
  csObject.Leave();
}

// 使用特殊的快速排序法排序 P 至 N 的節點
template <class T>
void cxxlFASTCALL cxxlList<T>::doSort(Node *P,Node *N)
{
  // 看找到的位置偏左(R_ps 比較大)或偏右(L_ps 比較大)
  unsigned long int L_ps;
  unsigned long int R_ps;

  int dir;      // 決定哪一端移動，-1 右端移動，1 左端移動
  Node *L,*R;

  while(P != N)
  {
    R_ps = L_ps = 0;
    L = P; R = N;
    dir = -1;
    while(L != R)
    {
      if(Diagnosis(L->Obj_Ptr,R->Obj_Ptr) == false)
      {
        Swap(L,R);
        dir = -dir;
      }

     	if(dir == 1)
      {
        L = L->next; L_ps++;
      }
      else
      {
     	  R = R->prev; R_ps++;
      }
    }

    // 只讓較少的那邊用遞迴繼續排序，較多的那邊撟一下後，在本地繼續排序
    if(L_ps > R_ps)
    {
      if(L != N)
        doSort(L->next,N);
      N = L->prev;
    }
    else  // ps < 0
    {
      if(L != P)
        doSort(P,L->prev);
      P = L->next;
    }
  }
}

}   /* namespace CxxlMan */
#endif
